1. Field of the Invention:
The method and apparatus of the present invention is related to the field of the generation of computer generated images. In particular, the method and apparatus of the present invention is related to the shading of computer generated images.
2. Art Background:
Typically, in a computer graphics system which generates digital images, the surfaces of objects are represented as a mesh of planar polygons. These polygons can be transformed and rendered quickly using well-known techniques. The techniques assume the input to be a simple triangle where the vertex attributes are position, normal and color as illustrated in FIG. 1a. The vertex position is defined, for example, in the object coordinate space. The vertex normals are unit vectors which describe the the surface orientation at each vertex. The vertex color specifies the intrinsic color of the object. The vertex color attribute allows the object color to vary across the triangle.
In order to generate a realistic image of an object on a computer graphics display, not only must the shape of the object be generated but the shading of the visible surfaces of the object must be included, taking into account the light sources, surface characteristics and the positions and orientations of the surfaces and sources. A combination of three reflection functions may be used to determine the shading of an image. Those three reflection functions are ambient reflection, diffuse reflection and specular reflection. Ambient reflection is the light which the object absorbs, then radiates, from random light sources. There is no dependence on light direction. The ambient function simply scales the object color. For example, for the ambient weights for red, green and blue, Ka.sub.r, Ka.sub.g, Ka.sub.b, the function of ambient reflection may be described as: EQU la.sub.r =Ka.sub.r *C.sub.r EQU la.sub.g =Ka.sub.g *C.sub.g EQU la.sub.b =Ka.sub.b *C.sub.b
where la.sub.r, la.sub.g, la.sub.b respectively are the ambient reflection for the red, green and blue color elements, Ka.sub.r, Ka.sub.g, Ka.sub.b are the ambient weights for the color elements red, green and blue and C.sub.r, C.sub.g, C.sub.b are the object color or color intensities for the red, green and blue elements of the object. The range of the ambient weights is: EQU 0.ltoreq.Ka.sub.r .ltoreq.1, 0.ltoreq.Ka.sub.g .ltoreq.1, 0.ltoreq.Ka.sub.b .ltoreq.1.
It should be noted that the ambient weights, Ka.sub.r, Ka.sub.g, Ka.sub.b, and the diffuse weights, Kd.sub.r, Kd.sub.g, Kd.sub.b below are, in fact, the product of two terms. The first term expresses the light intensity for the component. The second term expresses the ability of the object surface to reflect this component. Since neither depends on the scene geometry, the discussion combines the two terms into the weights. If the scene includes multiple light sources, there would be separate weights for each light source.
Dull, matted surfaces exhibit diffuse reflections, scattering light equally in all directions so that surfaces appear to have the same brightness from all viewing angles. For such surfaces, Lambert's cosine law relates the amount of reflected light to the cosine of the angle .alpha. between the direction L to the point light source, and the normal vector N to the surface as is illustrated in FIG. 1b. The diffuse reflection may be represented by the following equation: EQU ld.sub.r =cos (.alpha.)*Kd.sub.r *C.sub.r EQU ld.sub.g =cos (.alpha.)*Kd.sub.g *C.sub.g EQU ld.sub.b =cos (.alpha.)*Kd.sub.b *C.sub.b
where cos (.alpha.) equals N.multidot.L (Since the diffuse reflection must be positive, the calculation of the cos (.alpha.) requires: cos (.alpha.)=max(cos (.alpha.),0).), ld.sub.r, ld.sub.g, ld.sub.b respectively are the diffuse reflection values for the red, green, and blue elements, Kd.sub.r, Kd.sub.g and Kd.sub.b are the diffuse reflection coefficients for the red, green and blue elements of the light source (which are a constant between 0 and 1 and vary according to the material of the surface), and C.sub.r, C.sub.g and C.sub.b are the colors of red, green and blue elements of the surface.
Specular reflection is the highlight observed on a shiny surface. The model developed by Bui Tuong-Phong modulates specular reflection as a function of the cosine of the angle between V, the vector to the eyepoint, and R, the vector which aligns with the maximum reflection as illustrated in FIG. 1b (Phong, B. T. "Illumination for Computer Generated Images", PhD Dissertation, Dept. of Computer Science, University of Utah, Salt Lake City, Gov. Ordering No. AD-A0008-786 (July 1973)). For further information on ambient, diffuse and specular reflection, see also Foley and Van Dam Fundamentals of Interactive Computer Graphics, (Addison Wesley 1983), pp. 575-580 and Cook and Torrance, "A Reflectance Model For Computer Graphics", Computer Graphics, Vol. 15, No. 3, August 1981.
The amount of reflection is additive. Thus, if 3 separate light sources shine light on a surface, the amount of reflection on the surface is compute by determining the amount of reflection with respect to each light source and summing the amount of reflection determined with respect to each light source. When determining the type of reflection and amount of reflection, it should be recognized that there exists different types of light sources. One case occurs if the solution assumes the distance to the light is infinite. The specification for the light source reduces to the simple light vector below: EQU L=Lx, Ly, Lz
where the magnitude of the light vector equals, EQU .vertline.L.vertline.=sqrt (Lx.sup.2 +Ly.sup.2 +Lz.sup.2)
and the value of .vertline.L.vertline. equals 1 for an infinite light source.
Another case occurs if the solution assumes the distance to the light is finite but the radiation pattern is isotopic. The light therefore radiates the same intensity in all directions. The specification of the light source in this case reduces to the light position: EQU Q=Qx, Qy, Qz.
The light vector, that is the light position relative to the vertex position, Px, Py, Pz, is: EQU L=Qx-Px, Qy-Py, Qz-Pz
where the magnitude is: EQU .vertline.L.vertline.=sqrt ((Qx-Px).sup.2 +(Qy-Py).sup.2 +(Qz-Pz).sup.2).
Since the magnitude may not be one, and the illumination equations require unit vectors, the light vector is normalized: EQU L=(Qx-Px)/.vertline.L.vertline., (Qy-Py)/.vertline.L.vertline., (Qz-Pz)/.vertline.L.vertline..
Still another case occurs when the radiation pattern is not isotopic. Since the radiation pattern is not isotopic, the specification of the light source requires the pattern vector which specifies the radiation pattern function: EQU K=Kx,Ky,Kz.
The pattern vector serves to describe the direction where the light intensity is maximum. The light which strikes the object then decreases as the angle between the light vector, L, and the pattern vector, K, increases. The light vector, before inclusion of the pattern function is as before: EQU L=(Qx-Px)/.vertline.L.vertline., (Qy-Py)/.vertline.L.vertline., (Qz-Pz)/.vertline.L.vertline.
where the magnitude is EQU .vertline.L.vertline.=sqrt ((Qx-Px).sup.2 +(Qy-Py).sup.2 +(Qz-Pz).sup.2).
The pattern function, which adjusts the intensity as a function of the angle between the light vector and the pattern vector, is often: EQU cos (.kappa.)=Kx*Lx+Ky*Ly+Kz*Lz.
The light vector absorbs this value to become: EQU L=cos (.kappa.)*Lx, cos (.kappa.)*Ly, cos (.kappa.)*Lz.
Computer graphics systems typically represent curved surfaces of images as a mesh of planar polygons that are shaded to restore a smooth appearance. The systems attempt to restore the smooth appearance by varying the intensity across the polygons. Although there are techniques for realistic shading of polygons, real time systems do not use them because of the large amount of computation required per pixel. The simplest shading computation that may be performed is the diffuse reflection computation, which follows Lambert's Law for diffuse light. However, this computation assumes the same brightness of reflection from all viewing angles. Since the simple diffuse equation does not cast the reflection equations in terms of the physical attributes of the surface, for example, a roughness coefficient, the expression only approximates the reflection. The expression, for example, does not described how the wavelength can shift with the incident angle when the light strikes metallic surfaces. This wavelength shift causes the color to change. In addition, the simple diffuse equation does not attempt to take into account how light scatters from surface to surface.
Furthermore, the simplest version of the diffuse reflection assumes the reflection is constant across the entire facet or polygon. While this is simple to compute, the intensity is often discontinuous at the boundary between polygons. A better technique for performing shading of images in real time is referred to as Gouraud Shading. In the Gouraud Shading technique, the intensity at each point is computed by the linear interpolation of the intensities at the vertices of the polygon. These intensities are determined using the reflection equation for diffuse reflection with the normals given at the vertices. For further information on the Gouraud Shading see, Gouraud, H. "Continuous Shading of Curved Surfaces", IEEE Transactions on Computers, Vol. 20, No. 6, pp. 623-628 (June 1971). However, this technique accounts solely for diffuse reflection and thus surfaces shaded by this technique appear dull. In addition, the images may reflect mach bands at polygon boundaries due to discontinuous intensity changes.
The Phong Shading technique illuminates the dull surfaces and reduces the mach bands which the Gouraud Shading technique produces, but typically is not used in real time systems because of the large amount of computation time and expense required for the generation of the image. In this technique, the intensity of each point is determined using an approximate surface normal that is linearly interpolated from the true surface normal specified at the vertices. Phong shading utilized the equation N(x,y)=Ax+By+C where A, B, C are the chosen vertices to interpolate the normal across the polygon. The Phong Shading equation requires 7 additions, 6 multiplications, 1 division and 1 square root per pixel. This operation is very expensive and time consuming, particularly because it includes the square root computation. For further information on Phong Shading, see Phong, B, T. "illustration for Computer Generated Images", PhD Dissertation, Dept. of Computer Science, University of Utah, Salt Lake City, Gov. Ordering No. AD-A0008-786.
The Phong Shading calculation was simplified by Tom Duff as described in "Smoothly Shaded Renderings of Polyhedral Objects on Raster Displays", ACM Computer Graphics, Vol. 13, No. 2, pp. 270-275 (1979). Duff simplified Phong shading by combining the interpolation and reflection equations: ##EQU1## Thus this implementation can be evaluated for successive values of x and y with only 3 additions, 1 division and 1 square root per pixel. Although this is an improvement over Phong's formulation, the division and square root computations still render the technique too time consuming and expensive for real time implementation.
In still another implementation of Phong's shading, an approximation of the r eflection equation is computed, there by saving the time and expense required to compute the reflection equation exactly. In Weimer, "Fast Phong Shading", Computer Graphics, Vol. 20, No. 4, (1986), pp. 103-105, a second order Taylor series approximation is used to compute the reflection. To simplify the approximation, the polygon is shifted so that the (0,0) coordinate lies at the center of the polygon. Using this technique, the intensity at a pixel can be evaluated using only two additions per pixel.
However, in all the above techniques, the same functions are used to determine the reflection of all polygons of an image. If the reflection for some of the polygons of the image can only be determined at the desired level of quality using a complex, time consuming process, all polygons are processed using the same process. Thus, to render a quality image, a complex time consuming process is employed to get desired quality for the image, even though the reflection for a significant number of polygons could have been determined using a simpler faster process.